
//设计一个算法，求一个数组中最小的k个数

class Solution {
    public int[] smallestK(int[] arr, int k) {
            int[] ret=new int[k];
            if(arr==null||k==0){
                return ret;
            }
            //建立大根堆
             Queue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {//堆默认是小根堆排序，所以需要重写比较方法
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });
            //遍历前k个数，放到堆中
            for(int i=0;i<k;i++){
                queue.offer(arr[i]);
            }
            
            //遍历剩下的元素
            for(int i=k;i<arr.length;i++){
               int val=queue.peek();
                if(arr[i]<val){
                  queue.poll();
                  queue.offer(arr[i]);
                }
                
            
            }
            for(int i=0;i<k;i++){
                ret[i]=queue.poll();
            }
            return ret;
    }
}